package huaweiOD;

import java.util.Stack;

/**
 * Project: tobe-better-coder
 * Package: huaweiOD
 *
 * 给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。
 *
 * 返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现 至少 repetition 次。
 *
 * 子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。
 *
 * 字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b的字符
 *
 * @author : Mr.xu
 * @date : 2023/5/13 7:00
 */
public class SmallestSubsequence {

    public String method(String s,int k,char letter,int repetition){
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        int letterCount = 0;
        for (int i = 0; i < arr.length; i++) {
            if (letter == arr[i]) letterCount++;
        }
        int n = s.length();
        int curLetter = 0;
        for (int i = 0; i < arr.length; i++) {
            //1,判断是否为null，2,当前这个字符是不是更优，3,之后的字符可以组成k个，4，letter字符是否不够
            //5，是否没有位置添加letter字符
            while ((!stack.isEmpty() && stack.peek() > arr[i] && n - i + stack.size() - 1 >= k
                    && curLetter - (stack.peek() == letter ? 1 : 0) + letterCount >= repetition)
                    || curLetter + k - stack.size() < repetition) {
                Character pop = stack.pop();
                if (pop == letter) curLetter--;
            }

            if (stack.size() < k) {
                if (arr[i] == letter) curLetter++;
                stack.push(arr[i]);
            }

            if (arr[i] == letter) letterCount--;
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}